import java.util.Arrays;

public class E06Fibonacci {

    public static void main(String[] args) {
//        long start = System.currentTimeMillis();
//        System.out.println(e06Fibonacci(45 ));
//        System.out.println((System.currentTimeMillis() - start));
//        System.out.println("____________________________________");
        long start2 = System.currentTimeMillis();
        System.out.println(runE06Fibonacci2(1000 ));
        System.out.println((System.currentTimeMillis() - start2));
    }

    /**
     * 普通递归求斐波那契数列
     * @param index
     * @return
     */
    public static long e06Fibonacci(long index){
        if (index == 1){
            return 1L;
        }
        if (index == 0L){
            return 0L;
        }

        return e06Fibonacci(index - 1L) + e06Fibonacci(index - 2L);
    }



    public static long runE06Fibonacci2(long index){
        long[] cache = new long[(int) (index + 1L)];
        Arrays.fill(cache,-1L);
        cache[0] = 0L;
        cache[1] = 1L;

        return e06Fibonacci2(index,cache);
    }

    /**
     * 记忆法
     * @param index
     * @return
     */
    public static long e06Fibonacci2(long index,long[] cache){
        if (cache[(int) index] != -1L) {
            return cache[(int) index];
        }
        long x = e06Fibonacci2(index - 1L, cache) + e06Fibonacci2(index - 2L, cache);
        cache[(int) index] = x;
        return x;
    }


}
